{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Ways to Group Overlapping Ranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计将重叠区间合并成组的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>ranges</code>&nbsp;，其中&nbsp;<code>ranges[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>&nbsp;表示&nbsp;<code>start<sub>i</sub></code>&nbsp;到&nbsp;<code>end<sub>i</sub></code>&nbsp;之间（包括二者）的所有整数都包含在第&nbsp;<code>i</code>&nbsp;个区间中。</p>\n",
    "\n",
    "<p>你需要将&nbsp;<code>ranges</code>&nbsp;分成 <strong>两个</strong>&nbsp;组（可以为空），满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个区间只属于一个组。</li>\n",
    "\t<li>两个有 <strong>交集</strong>&nbsp;的区间必须在 <strong>同一个&nbsp;</strong>组内。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果两个区间有至少 <strong>一个</strong>&nbsp;公共整数，那么这两个区间是 <b>有交集</b>&nbsp;的。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，区间&nbsp;<code>[1, 3]</code> 和&nbsp;<code>[2, 5]</code>&nbsp;有交集，因为&nbsp;<code>2</code>&nbsp;和&nbsp;<code>3</code>&nbsp;在两个区间中都被包含。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回将 <code>ranges</code>&nbsp;划分成两个组的 <strong>总方案数</strong>&nbsp;。由于答案可能很大，将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>ranges = [[6,10],[5,15]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "两个区间有交集，所以它们必须在同一个组内。\n",
    "所以有两种方案：\n",
    "- 将两个区间都放在第 1 个组中。\n",
    "- 将两个区间都放在第 2 个组中。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>ranges = [[1,3],[10,20],[2,5],[4,8]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。\n",
    "同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。\n",
    "所以总共有 4 种分组方案：\n",
    "- 所有区间都在第 1 组。\n",
    "- 所有区间都在第 2 组。\n",
    "- 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。\n",
    "- 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= ranges.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>ranges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-ways-to-group-overlapping-ranges](https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-ways-to-group-overlapping-ranges](https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[6,10],[5,15]]', '[[1,3],[10,20],[2,5],[4,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        \n",
    "        ranges.sort()\n",
    "        \n",
    "        n = len(ranges)\n",
    "        \n",
    "        cands = []\n",
    "        \n",
    "        for a, b in ranges:\n",
    "            cands.append((a, 0))\n",
    "            cands.append((b, 1))\n",
    "        \n",
    "        cands.sort()\n",
    "        ans = 0\n",
    "        ops = 0\n",
    "        for x, status in cands:\n",
    "            if status == 0:\n",
    "                ops += 1\n",
    "            else:\n",
    "                ops -= 1\n",
    "                if not ops: ans += 1\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        M = 10 ** 9 + 7\n",
    "        \n",
    "        return pow(2, ans, M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        n = len(ranges)\n",
    "        ranges.sort()\n",
    "        res = []\n",
    "        count1 = 0\n",
    "        count2 = 0\n",
    "        for i in range(n):\n",
    "            if not res:\n",
    "                res.append(ranges[i])\n",
    "            else:\n",
    "                if ranges[i][0] <= res[-1][1]:\n",
    "                    tmp = res.pop()\n",
    "                    left = min(tmp[0], ranges[i][0])\n",
    "                    right = max(tmp[1], ranges[i][1])\n",
    "                    res.append([left, right])\n",
    "                else:\n",
    "                    res.append(ranges[i])\n",
    "        count = len(res)\n",
    "        return 2 ** count % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        ranges.sort()\n",
    "        n = len(ranges)\n",
    "        end = ranges[0][1]\n",
    "        for i in range(1, n):\n",
    "            if ranges[i][0] <= end:\n",
    "                n -= 1\n",
    "            end = max(end, ranges[i][1])\n",
    "        res = 1\n",
    "        for _ in range(n):\n",
    "            res = res * 2 % M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        pre = ranges[0]\n",
    "        range_cnt = 1\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0] <= pre[1]:\n",
    "                pre[1] = max(ranges[i][1], pre[1])\n",
    "            else:\n",
    "                pre = ranges[i]\n",
    "                range_cnt += 1\n",
    "        # print(ranges)\n",
    "        ans = 1\n",
    "        while range_cnt > 0:\n",
    "            ans = int((ans * 2) % (1e9 + 7))\n",
    "            range_cnt -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges = list(sorted(ranges, key = lambda x: x[0]))\n",
    "        l = ranges[0][1]\n",
    "        r = 1\n",
    "        for item in ranges:\n",
    "            if item[0] > l: r += 1\n",
    "            l = max(item[1], l)\n",
    "        return pow(2, r,  10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        n = len(ranges)\n",
    "        if n==1:\n",
    "            return 2\n",
    "        cnt = 1\n",
    "        a,b = ranges[0]\n",
    "        i = 1\n",
    "        while i <n:\n",
    "            a1,b1 = ranges[i]\n",
    "            if a1<=b:\n",
    "                b = max(b,b1)\n",
    "            else:\n",
    "                cnt+=1\n",
    "                a,b = a1,b1\n",
    "            i+=1\n",
    "        return pow(2,cnt,1000000007)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        dp = 1\n",
    "        M = 1_000_000_007\n",
    "        bound = ranges[0][1]\n",
    "        for c, d in ranges[1:]:\n",
    "            if bound < c: dp = 2 * dp % M\n",
    "            if d > bound: bound = d\n",
    "        return 2 * dp % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    " \n",
    "        MOD = int(1e9+7)\n",
    "        ranges.sort()\n",
    "\n",
    "        l,r = ranges[0]\n",
    "        cnt = 1\n",
    "        ans = 1\n",
    "\n",
    "        for i, (l2,r2) in enumerate(ranges):\n",
    "            if r < l2:\n",
    "                cnt += 1\n",
    "            r = max(r, r2)\n",
    "\n",
    "        for i in range(cnt):\n",
    "            ans *= 2\n",
    "            if ans > MOD:\n",
    "                ans -= MOD\n",
    "\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self,n):\n",
    "        self.parents = list(range(n))\n",
    "        self.sizes = [1]*n\n",
    "        self.union_cnt = n\n",
    "    def find(self,x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self,x,y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        if(self.sizes[ax] > self.sizes[ay]):\n",
    "            ax, ay = ay, ax\n",
    "        self.parents[ax] = ay \n",
    "        self.sizes[ay] += self.sizes[ax]\n",
    "        self.union_cnt -= 1\n",
    "        return False\n",
    "    \n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        n = len(ranges)\n",
    "        cnt = 1\n",
    "        # us = UnionSet(n)\n",
    "        start, end = ranges[0]\n",
    "        for i in range(1,n):\n",
    "            s, e = ranges[i]\n",
    "            if(s <= end):\n",
    "                # us.union(i-1,i)\n",
    "                end = max(end, e)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                start = s \n",
    "                end = e \n",
    "        return 2**cnt % (10**9+7)\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ret = []\n",
    "        for x, y in sorted(ranges, key=lambda x: x[0]):\n",
    "            if not ret or x > ret[-1][-1]:\n",
    "                ret.append([x, y])\n",
    "            elif x <= ret[-1][-1]:\n",
    "                ret[-1][-1] = max(ret[-1][-1], y)\n",
    "        return pow(2, len(ret)) % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ret = [-1, -1]\n",
    "        ans = 0\n",
    "        for x, y in sorted(ranges, key=lambda x: x[0]):\n",
    "            if x > ret[-1]:\n",
    "                ret = [x, y]\n",
    "                ans += 1\n",
    "            elif x <= ret[-1]:\n",
    "                ret[-1] = max(ret[-1], y)\n",
    "        return pow(2, ans) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def fast_pow2(self, n):\n",
    "        if n<=2: return [1, 2, 4][n]\n",
    "        return self.fast_pow2(n//2)**2 * (1+n%2) %1000000007 \n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key = lambda x: x[0])\n",
    "        res, tmp_max = 1, ranges[0][1]\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0]>tmp_max: res += 1\n",
    "            tmp_max = max(tmp_max, ranges[i][1])\n",
    "        return self.fast_pow2(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self,n):\n",
    "        self.parents = list(range(n))\n",
    "        self.sizes = [1]*n\n",
    "        self.union_cnt = n\n",
    "    def find(self,x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self,x,y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        if(self.sizes[ax] > self.sizes[ay]):\n",
    "            ax, ay = ay, ax\n",
    "        self.parents[ax] = ay \n",
    "        self.sizes[ay] += self.sizes[ax]\n",
    "        self.union_cnt -= 1\n",
    "        return False\n",
    "    \n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        n = len(ranges)\n",
    "        cnt = 1\n",
    "        # us = UnionSet(n)\n",
    "        start, end = ranges[0]\n",
    "        for i in range(1,n):\n",
    "            s, e = ranges[i]\n",
    "            if(s <= end):\n",
    "                # us.union(i-1,i)\n",
    "                end = max(end, e)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                start = s \n",
    "                end = e \n",
    "        return 2**cnt % (10**9+7)\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        res = len(ranges)\n",
    "        for i in range(1, res):\n",
    "            if ranges[i-1][1]<ranges[i][0]:\n",
    "                continue\n",
    "            ranges[i][1] = max(ranges[i-1][1], ranges[i][1])\n",
    "            res -= 1\n",
    "        return 2**res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "        cnt = 1\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0] > ranges[i - 1][1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ranges[i][1] = max(ranges[i - 1][1], ranges[i][1])\n",
    "        return (2 ** cnt) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        n = len(ranges)\n",
    "        fa = list(range(n))\n",
    "        # fa = {x: x for x in nums}  # 另一种写法，x不连续\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x, y):\n",
    "            fa[find(y)] = find(x)\n",
    "\n",
    "        ranges.sort()\n",
    "        max_right = ranges[0][1]\n",
    "        for i in range(n - 1):\n",
    "            if max_right < ranges[i + 1][0]:  # 无交集\n",
    "                max_right = ranges[i + 1][1]\n",
    "                continue\n",
    "            union(i, i + 1)\n",
    "            max_right = max(max_right, ranges[i + 1][1])\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "        m = len(set(fa))\n",
    "        return pow(2, m, MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        pre = ranges[0]\n",
    "        range_cnt = 1\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0] <= pre[1]:\n",
    "                pre[1] = max(ranges[i][1], pre[1])\n",
    "            else:\n",
    "                pre = ranges[i]\n",
    "                range_cnt += 1\n",
    "        ans = 1\n",
    "        while range_cnt > 0:\n",
    "            ans = int((ans * 2) % (1e9 + 7))\n",
    "            range_cnt -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        \n",
    "        # 区间合并\n",
    "        def merge(intervals: List[List[int]]) -> int:\n",
    "            \n",
    "            intervals.sort()\n",
    "\n",
    "            res = []\n",
    "            res.append(intervals[0])\n",
    "\n",
    "            for i in range(1, len(intervals)):\n",
    "                # 区间1：[s1, e1]\n",
    "                # 区间2：[s2, e2]\n",
    "                e1, (s2, e2) = res[-1][1], intervals[i]\n",
    "                \n",
    "                if e1 < s2:\n",
    "                    # 区间无交集\n",
    "                    res.append(intervals[i])\n",
    "                else:\n",
    "                    # 合并区间：\n",
    "                    # - 区间有交集：s2 <= e1 < e2\n",
    "                    # - 区间包含：e1 >= e2\n",
    "\n",
    "                    res[-1][1] = max(e1, e2)\n",
    "            \n",
    "            return len(res)\n",
    "\n",
    "        # n 个区间划分为两组的方案数：2^n\n",
    "        return pow(2, merge(ranges), MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, a: List[List[int]]) -> int:\n",
    "        n=len(a)\n",
    "        ufs=list(range(n))\n",
    "        def find(x):\n",
    "            if x==ufs[x]:\n",
    "                return x\n",
    "            ufs[x]=find(ufs[x])\n",
    "            return ufs[x]\n",
    "        def union(x,y):\n",
    "            ux,uy=find(x),find(y)\n",
    "            if ux!=uy:\n",
    "                ufs[ux]=uy\n",
    "        c=0\n",
    "        a.sort()\n",
    "        for i in range(n):\n",
    "            l,r=a[i]\n",
    "            if l>a[c][1]:\n",
    "                c=i\n",
    "            else:\n",
    "                union(c,i)\n",
    "                if r>a[c][1]:\n",
    "                    c=i\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if i==find(i):\n",
    "                res+=1\n",
    "        mod=10**9+7\n",
    "        return pow(2,res,mod)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        pre = ranges[0]\n",
    "        range_cnt = 1\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0] <= pre[1]:\n",
    "                pre[1] = max(ranges[i][1], pre[1])\n",
    "            else:\n",
    "                pre = ranges[i]\n",
    "                range_cnt += 1\n",
    "        return pow(2, range_cnt, 10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key = lambda x: (x[0],x[1]))\n",
    "        c = 1\n",
    "        m = ranges[0][1]\n",
    "        for i in range(1,len(ranges)):\n",
    "            if m >= ranges[i][0]:\n",
    "                m = max(m,ranges[i][1])\n",
    "            else:\n",
    "                c += 1\n",
    "                m = ranges[i][1]\n",
    "        return (2 ** c )%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        right = ranges[0][1]\n",
    "        cnt = 1\n",
    "        for l, r in ranges:\n",
    "            if l <= right:\n",
    "                right = max(right, r)\n",
    "            else:\n",
    "                cnt += 1\n",
    "                right = r\n",
    "        return pow(2, cnt, 10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "def power(a, n):\n",
    "    ans = 1\n",
    "    while n:\n",
    "        if n&1==1: ans *= a\n",
    "        a *= a\n",
    "        n >>= 1\n",
    "    return ans\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "        cnt,  last_end = 1, ranges[0][1]\n",
    "        for s,e in ranges[1:]:\n",
    "            if s <= last_end:\n",
    "                last_end = max(last_end, e)\n",
    "            else:\n",
    "                last_end = e\n",
    "                cnt += 1\n",
    "        \n",
    "        return power(2,cnt) %MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key = lambda p: p[0])\n",
    "        cnt, maxr = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            if l > maxr:\n",
    "                cnt += 1\n",
    "            maxr = max(maxr, r)\n",
    "        return pow(2, cnt, 10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p : p[0]) # lambda expression \n",
    "        cnt = 1\n",
    "        max_r = ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            if l > max_r:\n",
    "                cnt += 1\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, cnt, 10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        dp, rBound = 1, -inf\n",
    "        M = 1_000_000_007\n",
    "        for c, d in sorted(ranges):\n",
    "            if rBound < c: dp = 2 * dp % M\n",
    "            if d > rBound: rBound = d\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "        m, maxR = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > maxR\n",
    "            maxR = max(maxR, r)\n",
    "        return pow(2, m, 10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fast_pow2(self, n):\n",
    "        if n<=2: return [1, 2, 4][n]\n",
    "        return self.fast_pow2(n//2)**2 * (1+n%2) %1000000007 \n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key = lambda x: x[0])\n",
    "        res, tmp_max = 1, ranges[0][1]\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0]>tmp_max: res += 1\n",
    "            tmp_max = max(tmp_max, ranges[i][1])\n",
    "        return self.fast_pow2(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        # 按照是否有交集分组，2的组数次方就是答案，记得除以MOD\n",
    "        # 组数\n",
    "        group = 0\n",
    "        ranges.sort()\n",
    "        # 右边界，只要左边界小于它，就在一组中\n",
    "        right = -1\n",
    "        for l, r in ranges:\n",
    "            if l > right:\n",
    "                group += 1\n",
    "                right = r\n",
    "            elif r > right:\n",
    "                right = r\n",
    "\n",
    "        return pow(2, group, MOD)\n",
    "                \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        # 按照是否有交集分组，2的组数次方就是答案，记得除以MOD\n",
    "        # 组数\n",
    "        group = 0\n",
    "        ranges.sort()\n",
    "        # 右边界，只要左边界小于它，就在一组中\n",
    "        right = -1\n",
    "        for l, r in ranges:\n",
    "            if l > right:\n",
    "                group += 1\n",
    "                right = r\n",
    "            elif r > right:\n",
    "                right = r\n",
    "\n",
    "        return (1 << group) % MOD\n",
    "                \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "def power(a, n):\n",
    "    ans = 1\n",
    "    while n:\n",
    "        if n&1==1: ans *= a\n",
    "        a *= a\n",
    "        n >>= 1\n",
    "    return ans\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "        cnt,  last_end = 1, ranges[0][1]\n",
    "        for s,e in ranges[1:]:\n",
    "            if s <= last_end:\n",
    "                last_end = max(last_end, e)\n",
    "            else:\n",
    "                last_end = e\n",
    "                cnt += 1\n",
    "        \n",
    "        return pow(2,cnt) %MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        dp = 1\n",
    "        M = 1_000_000_007\n",
    "        bound = ranges[0][1]\n",
    "        for c, d in sorted(ranges)[1:]:\n",
    "            if bound < c: dp = 2 * dp % M\n",
    "            if d > bound: bound = d\n",
    "        return 2 * dp % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        num_diff = 1\n",
    "        max_range = ranges[0][-1]\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0] > max_range:\n",
    "                num_diff += 1\n",
    "            max_range = max(max_range, ranges[i][-1])\n",
    "        res = 1\n",
    "        for i in range(num_diff):\n",
    "            res = (res * 2) % 1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       res = 1\n",
    "       ranges.sort()\n",
    "       n = len(ranges)\n",
    "       i = 0\n",
    "       while i < n:\n",
    "          right = ranges[i][1]\n",
    "          j = i + 1\n",
    "          while j < n and ranges[j][0] <= right:\n",
    "             right = max(right, ranges[j][1])\n",
    "             j += 1\n",
    "          res <<= 1\n",
    "          res %= MOD\n",
    "          i = j\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        k = 0\n",
    "        pre = -1\n",
    "        for l,r in ranges:\n",
    "            if l > pre:\n",
    "                k += 1\n",
    "            pre = max(r,pre)\n",
    "        return (1<<k) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key = lambda x: x[0])\n",
    "        res, tmp_max = 1, ranges[0][1]\n",
    "        for i in range(1, len(ranges)):\n",
    "            if ranges[i][0]>tmp_max: res += 1\n",
    "            tmp_max = max(tmp_max, ranges[i][1])\n",
    "        x = 1\n",
    "        for i in range(res):\n",
    "            x = x*2%1000000007 \n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        dp = 1\n",
    "        M = 1_000_000_007\n",
    "        bound = ranges[0][1]\n",
    "        for c, d in ranges[1:]:\n",
    "            if bound < c: dp = 2 * dp % M\n",
    "            if d > bound: bound = d\n",
    "        return 2 * dp % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        f=-1\n",
    "        q=0\n",
    "        \n",
    "        ranges.sort()\n",
    "        for x in ranges:\n",
    "          if x[0]>f:\n",
    "            q+=1\n",
    "          f=max(f,x[1])\n",
    "        \n",
    "        return 2**q%(10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges = sorted(ranges, key=lambda x: x[0])\n",
    "        n_grp = 0\n",
    "        maxr = -1\n",
    "        for l, r in ranges:\n",
    "            if l > maxr:\n",
    "                n_grp += 1\n",
    "            maxr = max(maxr, r)\n",
    "        return pow(2, n_grp, int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countWays(self, ranges: List[List[int]]) -> int:\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         ranges.sort(key = lambda x : x[0])\n",
    "#         ans = []\n",
    "#         ans.append(ranges[0])\n",
    "#         n = len(ranges)\n",
    "#         for i in range(1, n):\n",
    "#             st,end = ranges[i][0], ranges[i][1]\n",
    "#             if st <= ans[-1][1]:\n",
    "#                 ans[-1][1] = max(ans[-1][1], end)\n",
    "#             elif st > ans[-1][1]:\n",
    "#                 ans.append([st,end])\n",
    "\n",
    "#         return pow(2, len(ans), MOD)\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        # 按照是否有交集分组，2的组数次方就是答案，记得除以MOD\n",
    "        # 组数\n",
    "        group = 0\n",
    "        ranges.sort()\n",
    "        # 右边界，只要左边界小于它，就在一组中\n",
    "        right = -1\n",
    "        for l, r in ranges:\n",
    "            if l > right:\n",
    "                group += 1\n",
    "                right = r\n",
    "            elif r > right:\n",
    "                right = r\n",
    "\n",
    "        return pow(2, group, MOD)\n",
    "                \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        # ranges.sort()\n",
    "        # res = 0\n",
    "        # l=-1\n",
    "        # r=-1\n",
    "        # while ranges:\n",
    "        #     s,e = ranges.pop(0)\n",
    "        #     if s>r:\n",
    "        #         res+=1\n",
    "        #         l,r=s,e\n",
    "        #     else:\n",
    "        #         r=max(r,e)\n",
    "        # #print(res)\n",
    "        # tt=1<<res\n",
    "        # ans = tt%(10**9+7)\n",
    "        # return ans\n",
    "            \n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            if l > max_r:\n",
    "                m += 1\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key = lambda p : p[0])\n",
    "        m = 1\n",
    "        max_val = ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            if l > max_val:\n",
    "                m += 1\n",
    "            max_val = max(max_val, r)\n",
    "        return pow(2,m,10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        count_c=1\n",
    "        max_c=ranges[0][1]\n",
    "        for l,r in ranges:\n",
    "            count_c += l>max_c\n",
    "            max_c=max(max_c,r)\n",
    "        return pow(2,count_c,10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        # ranges.sort()\n",
    "        # res = 0\n",
    "        # l=-1\n",
    "        # r=-1\n",
    "        # while ranges:\n",
    "        #     s,e = ranges.pop(0)\n",
    "        #     if s>r:\n",
    "        #         res+=1\n",
    "        #         l,r=s,e\n",
    "        #     else:\n",
    "        #         r=max(r,e)\n",
    "        # #print(res)\n",
    "        # tt=1<<res\n",
    "        # ans = tt%(10**9+7)\n",
    "        # return ans\n",
    "            \n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        def takeFirst(s):\n",
    "            return s[0]\n",
    "        ranges.sort(key = takeFirst)\n",
    "        count = len(ranges)\n",
    "        i = 1\n",
    "        maximum = ranges[0][1]\n",
    "        while(i < len(ranges)):\n",
    "            if ranges[i][0] <= maximum:\n",
    "                maximum = max(maximum, ranges[i][1])\n",
    "                count -= 1\n",
    "            else:\n",
    "                maximum = ranges[i][1]\n",
    "            i += 1\n",
    "        def qpow(x, y):\n",
    "            mod = 1000000007\n",
    "            if y == 0:\n",
    "                return 1\n",
    "            elif y == 1:\n",
    "                return x\n",
    "            elif y % 2 == 0:\n",
    "                a = (qpow(x, y // 2)) % mod\n",
    "                return a * a\n",
    "            elif y % 2 == 1:\n",
    "                return (qpow(x, y - 1) * x) % mod\n",
    "        return qpow(2, count) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "       k = 0\n",
    "       ranges.sort()\n",
    "       n = len(ranges)\n",
    "       i = 0\n",
    "       while i < n:\n",
    "          right = ranges[i][1]\n",
    "          j = i + 1\n",
    "          while j < n and ranges[j][0] <= right:\n",
    "             right = max(right, ranges[j][1])\n",
    "             j += 1\n",
    "          k += 1\n",
    "          i = j\n",
    "       return pow(2, k, MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        l=-1\n",
    "        r=-1\n",
    "        cnt=0\n",
    "        for s,e in ranges:\n",
    "            if s>r:\n",
    "                cnt+=1\n",
    "                l=s \n",
    "                r=e\n",
    "            elif e>r:\n",
    "                r=e \n",
    "        mod=10**9+7\n",
    "        return 2**cnt%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda p: p[0])\n",
    "        m, max_r = 1, ranges[0][1]\n",
    "        for l, r in ranges:\n",
    "            m += l > max_r  # 产生了一个新的集合\n",
    "            max_r = max(max_r, r)\n",
    "        return pow(2, m, 10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges=sorted(ranges,key = lambda x:(x[0],x[1]))\n",
    "        \n",
    "        ans=0\n",
    "        k=10**9+7\n",
    "        n=len(ranges)\n",
    "        i=0\n",
    "        while i<n-1:\n",
    "            if ranges[i][0]==ranges[i+1][0]:\n",
    "                while i<n-1 and ranges[i][0]==ranges[i+1][0]:\n",
    "                    i+=1\n",
    "            if ranges[i][1]<ranges[i+1][0]:\n",
    "                i+=1\n",
    "                ans+=1\n",
    "            elif ranges[i][1]>=ranges[i+1][0]:\n",
    "                x=ranges[i][1]\n",
    "                while i<n-1 and x>=ranges[i+1][0]:\n",
    "                    i+=1\n",
    "                    x=max(x,ranges[i][1])\n",
    "        return pow(2,ans+1)%k\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        n = len(ranges)\n",
    "        ranges.sort(key=lambda x: (x[0], x[1]))\n",
    "        ans = 1\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            mx_r = ranges[i][1]\n",
    "            while j < n:   \n",
    "                xj, yj = ranges[j]\n",
    "                if xj <= mx_r:\n",
    "                    mx_r = max(mx_r, yj)\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            i = j\n",
    "            ans *= 2\n",
    "            ans %= 10 ** 9 + 7\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Dsu:\n",
    "#     def __init(self, n):\n",
    "#         self.pa = list(range(n))\n",
    "#         self.rk = [1] * n\n",
    "    \n",
    "#     def find(self, x):\n",
    "#         if self.pa[x] != x:\n",
    "#             self.pa[x] = self.find(self.pa[x])\n",
    "#         return self.pa[x]\n",
    "    \n",
    "#     def union(self, x, y):\n",
    "#         x, y = self.find(x), self.find(y)\n",
    "#         if x != y:\n",
    "#             self.pa[x] = y\n",
    "#             self.rk[y] += self.rk[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: (x[0],x[1]))\n",
    "        m , max_r = 1,ranges[0][1]\n",
    "        for l,r in ranges:\n",
    "            m += l > max_r \n",
    "            max_r = max(max_r,r)\n",
    "        mode = 10 ** 9 + 7 \n",
    "        return pow(2,m,mode)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "\n",
    "        ranges.sort(key = lambda x:(x[0], x[1]))\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        start = ranges[0][0]\n",
    "        end = ranges[0][1]\n",
    "\n",
    "        for i in range(1, len(ranges)):\n",
    "            if end < ranges[i][0]:\n",
    "                ans *= 2\n",
    "                ans %= mod\n",
    "                start, end = ranges[i]\n",
    "            else:\n",
    "                end = max(end, ranges[i][1])\n",
    "        \n",
    "        ans *= 2\n",
    "        ans %= mod\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort()\n",
    "        res = list()\n",
    "        mod = 10 ** 9 + 7\n",
    "        for s, e in ranges:\n",
    "            if res and res[-1][1] >= s:\n",
    "                res[-1][1] = max(e, res[-1][1])\n",
    "            else:\n",
    "                res.append([s, e])\n",
    "        n = len(res)\n",
    "        # n = 5\n",
    "        # print(res)\n",
    "        ans = 1\n",
    "        a = 2\n",
    "        d = 2\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                ans *= a\n",
    "            a = (a * a) % mod\n",
    "            n >>= 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x:(x[0],x[1]))\n",
    "        L=[]\n",
    "        for i in range(len(ranges)):\n",
    "            [m,M]=ranges[i]\n",
    "            if L!=[] and M<=L[-1][1]:\n",
    "                continue\n",
    "            if L!=[] and m<=L[-1][1]<M:\n",
    "                m=L.pop()[0]\n",
    "            L.append([m,M])\n",
    "        s=len(L)\n",
    "        def pow(a,b):\n",
    "            flag=0\n",
    "            dic={0:a}\n",
    "            for i in range(1,len(bin(b)[2:])):\n",
    "                dic[i]=dic[i-1]*dic[i-1]\n",
    "            s=1\n",
    "            while b!=0:\n",
    "                if b&1==1:\n",
    "                    s=(s*dic[flag])%(10**9+7)\n",
    "                b=b>>1\n",
    "                flag+=1\n",
    "            return s\n",
    "        return pow(2,s)\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        ranges.sort(key = lambda x: x[0])\n",
    "        for start, end in ranges:\n",
    "            if not res:\n",
    "                res.append([start, end])\n",
    "            else:\n",
    "                if start <= res[-1][1]:\n",
    "                    res[-1][1] = max(res[-1][1], end)\n",
    "                else:\n",
    "                    res.append([start, end])\n",
    "        n = len(res)\n",
    "        num = pow(10, 9) + 7\n",
    "        return pow(2, n) % num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "def power(a, n):\n",
    "    ans = 1\n",
    "    while n:\n",
    "        if n&1==1: ans *= a\n",
    "        a *= a\n",
    "        n >>= 1\n",
    "    return ans\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "        interval = [ranges[0]]\n",
    "        for s,e in ranges[1:]:\n",
    "            if s <= interval[-1][1]:\n",
    "                interval[-1][1] = max(interval[-1][1], e)\n",
    "            else:\n",
    "                interval.append([s,e])\n",
    "        \n",
    "        return power(2,len(interval)) %MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ranges.sort(key = lambda x : x[0])\n",
    "        ans = []\n",
    "        ans.append(ranges[0])\n",
    "        n = len(ranges)\n",
    "        for i in range(1, n):\n",
    "            st,end = ranges[i][0], ranges[i][1]\n",
    "            if st <= ans[-1][1]:\n",
    "                ans[-1][1] = max(ans[-1][1], end)\n",
    "            elif st > ans[-1][1]:\n",
    "                ans.append([st,end])\n",
    "\n",
    "        return pow(2, len(ans), MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "       \n",
    "        # 存在的集合数*2 即可\n",
    "        ans = []\n",
    "        pre_left, pre_right = inf, inf\n",
    "        \n",
    "        for i, c in enumerate(ranges):\n",
    "            if i==0:\n",
    "                pre_left, pre_right = c[0], c[1]\n",
    "            else:\n",
    "                now_left, now_right = c[0], c[1]\n",
    "                if pre_left<=now_left<=pre_right:\n",
    "                    pre_left = min(now_left, pre_left)\n",
    "                    pre_right = max(now_right, pre_right)\n",
    "                else:\n",
    "                    ans.append([pre_left, pre_right])\n",
    "                    pre_left, pre_right = now_left, now_right\n",
    "        \n",
    "        ans.append([pre_left, pre_right])\n",
    "        \n",
    "        return pow(2,len(ans))%1000000007\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def countWays(self, ranges: List[List[int]]) -> int:\n",
    "        ranges.sort(key=lambda x: x[0])\n",
    "        interval = [ranges[0]]\n",
    "        for s,e in ranges[1:]:\n",
    "            if s <= interval[-1][1]:\n",
    "                interval[-1][1] = max(interval[-1][1], e)\n",
    "            else:\n",
    "                interval.append([s,e])\n",
    "        \n",
    "        return (2**len(interval)) %MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
